package by2019;

/*
 * 二叉搜索树
 * 每个节点左字树只包含比节点小的数
 * 每个节点右子树只包含比节点大的数
 * 每个子树都是二叉搜索数
 * 空数也属于二叉搜索树
 */

public class 验证二叉搜索树 {
	
	static int vae = Integer.MIN_VALUE ;

	public static void main(String[] args) {
		TreeNode tree = new TreeNode(0);
		//tree.left = new TreeNode(1) ;
		//tree.right = new TreeNode(3) ;
		
		boolean flag = isValidBST(tree) ;
		System.out.println(flag );
		//System.out.println(Integer.MIN_VALUE);
		
	}
	//将二叉树进行中序遍历，判断后一个数是否大于前一个数
    public static boolean isValidBST(TreeNode root) {
    	if(root==null)
    		return true ;
    	if(!isValidBST(root.left)) {
    		return false ;
    	}
    	if(root.val<vae) {
    		return false ;
    	}
    	vae = root.val ;
		return isValidBST(root.right);
        
    }
    
    //遍历左子树取一个最大值，遍历右子树取一个最小值
    //判断最大值是否小于树顶值，最小值是否大于树顶值
   
    public boolean isValidBSTPro(TreeNode root) {
		return false;
    }
    public boolean isBST(TreeNode root, long maxValue, long minValue) {
    	if(root==null)
    		return false ;
    	if(root.val >= maxValue || root.val <= minValue)
    		return false ;
    	return isBST(root.left, root.val, minValue) && isBST(root.right, maxValue, root.val);
    }
}

class TreeNode{
	     int val;
	     TreeNode left;
	     TreeNode right;
	     TreeNode(int x) { val = x; }
}
